package com.ds.bintree.LeetCode;

import java.util.Deque;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

/**
 * @author Dianzhi Han
 * @version 1.0
 * @description: TODO
 * @date 2022/9/14 14:37
 */
public class Num958_IsCompleteTree2 {
    public boolean isCompleteTree(TreeNode root) {
        Map<TreeNode,Integer> map =new HashMap<>();
        Deque<TreeNode> queue = new LinkedList<>();
        if(root==null){
            return true;
        }
        map.put(root,1);
        queue.offer(root);
        while (!queue.isEmpty()){
            TreeNode temp=queue.poll();
            if (temp.left!=null){
                queue.offer(temp.left);
                map.put(temp.left,map.get(temp)*2);
            }
            if (temp.right!=null){
                queue.offer(temp.right);
                map.put(temp.right,map.get(temp)*2+1);
            }
        }
        int max = 0;
        for (Map.Entry<TreeNode,Integer> entry:map.entrySet()){
            max=Math.max(max,entry.getValue());
        }
        return map.size() == max;
    }
}
